/*
 * @lc app=leetcode.cn id=738 lang=javascript
 *
 * [738] 单调递增的数字
 */

// @lc code=start
/**
 * @param {number} N
 * @return {number}
 */
var monotoneIncreasingDigits1 = function(N) {
    if (N < 10) return N
    let stack = []
    let n = N
    while (n > 0) {
        stack.unshift(n % 10)
        n = Math.floor(n / 10)
    }
    console.log(stack)
    let i = 1
    while (i < stack.length && stack[i-1] <= stack[i]) i += 1

    if (i < stack.length) {
        while (i > 0 && stack[i - 1] > stack[i]) {
            stack[i-1] -= 1
            i--
        }
        for (i+=1; i < stack.length; i++) {
            stack[i] = 9
        }
    }

    let num = 0
    for (let i = 0; i < stack.length; i++) {
        num = num * 10 + stack[i]
    }
    console.log(num)
};

var monotoneIncreasingDigits2 = function(N) {
    let ans = 0, seed = 1
    let p = N
    while (p > 0) {
        let low = p % 10
        p = Math.floor(p / 10)
        let high = p % 10
        if (high < low) {
            ans = 10 * seed - 1
            p -= 1
        } else {
            ans += (low * seed)
        }
        seed *= 10
    }
    console.log(ans)
}

var monotoneIncreasingDigits = function(N) {
    let max = -1, idx = -1
    let str = String(N).split('')
    for (let i = 0; i < str.length; i++) {
        if (max < str[i]) {
            max = str[i]
            idx = i
        }
        if (str[i] > str[i+1]) {
            str[idx] -= 1
            for (let j = idx + 1; j < str.length; j++) {
                str[j] = 9
            }
            break
        }
    }
    console.log(+str.join(''))
    return +str.join('')
}

// @lc code=end

monotoneIncreasingDigits(123425678)
